package backtrackingalgorithm;

import dynamicprogramming.Example1;
import org.junit.Test;

/**
 * @author DuJiabao
 * @create 2021-01-01 23:53
 */
public class Bag {
    protected int maxW = Integer.MIN_VALUE; // 结果放到maxW中
    protected int[] weight = {2, 2, 4, 6, 3}; // 物品重量
    protected int n = 5; // 物品个数private
    protected int w = 9; // 背包承受的最大重量
    private boolean mem[][] = new boolean[n][w + 1]; //记录处理过的状况

    /**
     * @param n 第n个物品
     * @param w 当前重量
     */
    public void f(int n, int w) {
        if (n == this.n || w == this.w) {
            maxW = Math.max(w, maxW);
            return;
        }
        // 如果已经处理过当前情况，则直接return
        if (mem[n][w]) {
            return;
        }
        mem[n][w] = true;

        f(n + 1, w);
        if (w + weight[n] <= this.w) {
            f(n + 1, w + weight[n]);
        }
    }

    @Test
    public void test() {
        f(0, 0);
        System.out.println(maxW);
    }
}
